package main

import "fmt"

func main() {
	nums := []int{56, 1, 22, 23, 54, 16, 17, 9, 34}
	mergeSort(nums)
	fmt.Println(nums)
}

func mergeSort(nums []int) {
	mergeSortHelper(nums)
}

func mergeSortHelper(nums []int) {
	if len(nums) <= 1 {
		return
	}
	mid := len(nums) / 2
	mergeSortHelper(nums[:mid])
	mergeSortHelper(nums[mid:])
	merge(nums, mid)
}

func merge(source []int, right int) {
	i, j := 0, right
	tmp := make([]int, len(source))
	for k, _ := range source {
		if i == right {
			tmp[k] = source[j]
			j++
		} else if j == len(source) {
			tmp[k] = source[i]
			i++
		} else {
			if source[i] < source[j] {
				tmp[k] = source[i]
				i++
			} else {
				tmp[k] = source[j]
				j++
			}
		}
	}
	copy(source, tmp)
}
